#include <stdio.h>
#include <malloc.h>
/*归并排序*/

/*分而治之*/


typedef struct Node
{
    int data;
    struct Node *next;
}Node;

typedef struct List
{
    Node *head;
    size_t length;
}List;

Node* CreateNode(int data)
{
    Node *new_node = (Node *)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

void InitList(List **list)
{
    if (*list)
    {
        return;
    }

    (*list) = (List *)malloc(sizeof(List));
    (*list)->head = NULL;
    (*list)->length = 0;
    
}

List* PushBackNode(List *list,int data)
{
    if (list == NULL)
    {
        perror("uninit");
        return NULL;
    }
    
    Node *new_node = CreateNode(data);
    if (!new_node)
    {
        perror("unmemory");
        return list;
    }
    
    if (list->head == NULL)
    {
        list->head = new_node;
    }
    else 
    {
        Node *temp = list->head;
        while (temp->next)
        {
            temp = temp->next;
        }
        temp->next = new_node;
    }

    list->length ++;
    return list;
}

void PrintList(List *list)
{
    if (!list || !list->head)
    {
        return;
    }
    
    Node *temp = list->head;
    printf("PrintList:\n");
    printf("[");
    while (temp)
    {
        printf(" %d ",temp->data);
        temp = temp->next;
    }
    printf("]");
    printf("\n");
}

void PrintHead(Node *head)
{
    if (!head)
    {
        return;
    }
    
    Node *temp = head;
    printf("PrintHead:\n");
    printf("[");
    while (temp)
    {
        printf(" %d ",temp->data);
        temp = temp->next;
    }
    printf("]");
    printf("\n");
}

void PrintMergeHead(Node *head)
{
    if (!head)
    {
        return;
    }
    
    Node *temp = head;
    printf("PrintMergeHead:\n");
    printf("[");
    while (temp)
    {
        printf(" %d ",temp->data);
        temp = temp->next;
    }
    printf("]");
    printf("\n");
}

/*两个有序表合并成一个*/
//合并两个已排序的子数组 arr[left..middle] 和 arr[middle+1..right]  
void Merge(int arr[],int left,int middle,int right)
{
    int size = middle - left + 1;
    int *temp = (int *)malloc(sizeof(arr[0]) * size);/*申请一个空间来暂存左边的数组*/

    /*将左子数组的元素复制到 temp  */
    for (size_t i = 0; i < size; i++)
    {
        temp[i] = arr[left + i];
    }
    

    int i = 0, j = middle + 1, k = left;  
    while (i < size && j <= right)
    {  
        if (temp[i] <= arr[j])
        {  
            arr[k++] = temp[i++];/*左边赋值*/
        } 
        else
        {  
            arr[k++] = arr[j++];/*右边赋值*/
        }  
    }
    
    /*如果有一边先结束，就把另一边剩余的赋值到输出数组中*/
    while (i < size)
    {
        arr[k ++] = temp[i ++];/*只管左边，右边本来就在arr中*/
    }
    // while (j <= right)
    // {
    //     arr[k ++] = temp[j ++];
    // }

    free(temp);
    
}

void MergeSort(int arr[],int left,int right)
{
    if (left >= right)
    {
        return;/**/
    }
    
    int middle = (left + right) / 2;/*每次归并都需要获取中间值*/

    /*左右两段分别再次归并*/
    MergeSort(arr,left,middle);
    MergeSort(arr,middle + 1,right);
    
    /*有序序列的合并*/
    Merge(arr,left,middle,right);

}


/*快慢指针找中点*/
Node *FindMiddle(Node *head)
{
    if (!head)
    {
        return head;
    }
    
    Node *slow = head;
    Node *fast = head->next;

    if (!fast)
    {   
        return head;  
    } 

    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

/*合并两个有序链表*/
Node* MergeList(Node *left, Node *right)
{  
    if (left == NULL) return right;  
    if (right == NULL) return left;  
  
    Node *result = NULL;  
  
    if (left->data <= right->data) {  
        result = left;  
        result->next = MergeList(left->next, right);  
    } else {  
        result = right;  
        result->next = MergeList(left, right->next);  
    }  
    PrintMergeHead(result);
    return result;  
}  

Node* MergeSortList(Node *head)
{
    PrintHead(head);
    if (head == NULL || head->next == NULL)
    {
        return head;
    }

    /*快慢指针找中点*/
    Node *middle = FindMiddle(head);

    Node *right = middle->next;/*右边*/
    middle->next = NULL;/*中间开始断开链表*/

    Node *Left = MergeSortList(head);
    Node *Right =  MergeSortList(right);
    
    return MergeList(Left,Right);
}

List *list = NULL;
int main(int argc, char const *argv[])
{
    InitList(&list);
    PushBackNode(list,2);
    PushBackNode(list,1);
    PushBackNode(list,5);
    PushBackNode(list,3);
    PushBackNode(list,7);
    PushBackNode(list,6);
    PushBackNode(list,1);
    PushBackNode(list,5);
    PushBackNode(list,3);
    PushBackNode(list,7);
    PushBackNode(list,6);
    PrintList(list);
    list->head = MergeSortList(list->head);
    PrintList(list);
    return 0;
}
